package com.acwing.partition10;

import java.io.*;

/**
 * @author `RKC`
 * @date 2021/11/30 20:27
 */
public class AC902最短编辑距离 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        reader.readLine();
        String s1 = reader.readLine();
        reader.readLine();
        String s2 = reader.readLine();
        writer.write(dynamicProgramming(s1, s2) + "\n");
        writer.flush();
    }

    private static int dynamicProgramming(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 0; j <= m; j++) dp[0][j] = j;
        //如果两个字符相等，不需要进行操作，记录状态的转移即可；如果两个字符不相等，
        //当前的最小操作次数可以由串a[0, i - 1]加上一个字符（dp[i - 1][j] + 1）
        //或者串a[0, i]替换一个字符（替换后要使a[i]等于b[j]，因此最小操作数就是dp[i - 1][j - 1] + 1），
        //又或者是删除掉a当前字符，删除a[i]等价于给b[j - 1]添加一个字符a[i]，使得两者相等，dp[i][j - 1] + 1
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
            }
        }
        return dp[n][m];
    }
}
